﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.StringCode
{
    class ReverseString
    {
        //============================== 力扣344 反转字符串
        //编写一个函数，其作用是讲输入的字符串反转过来。输入字符串以字符数组char[]的形式给出
        //必须原地修改数组。使用O(1)的额外空间解决这一问题
        public void ReverseString_1(char[] s)
        {//双指针法
            int left = 0, right = s.Length - 1;
            
            while(left < right)
            {
                char tmp = s[left];
                s[left] = s[right];
                s[right] = tmp;

                left++;
                right--;
            }

            foreach(char i in s)
            {
                Console.Write(i);
                
            }
        }
        //========================== 力扣541 反转字符串2
        //给定一个字符串s和一个整数k，你需要对从字符串开头算起的每隔2k个字符的钱k个字符进行反转
        //如果剩余字符少于k个，则将剩余字符全部反转
        //如果剩余字符小于2k但大于等于k，则反转前k个字符，其余保持原样
        //输入：s = "abcdefg",k=2
        //输出："bacdefg"
        public string ReverseStr_2(string s, int k)
        {
            char[] result = s.ToArray();
            for(int i = 0;i< result.Length;i+=(2*k))
            {
                //每隔2k个字符的前k个字符进行反转
                //剩余字符小于2k但大于等于k个则反转前k个字符
                if(i+k <= result.Length)
                {
                    Array.Reverse(result, i,  k);
                    continue;
                }
                //剩余字符少于k个，则将剩余字符进行反转
                Array.Reverse(result, i, result.Length-i);
            }
            return new string(result);
        }

        //======================= 力扣151 反转字符串里的单词
        //给你一个字符串s，逐个反转字符串中的所有单词
        //单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开
        //请你返回一个反转s中的单词顺序并用单个空格相连的字符串
        //要求：返回的字符串中只有单词间有单个空格
        // 不是用split库函数，不使用辅助空间，空间复杂度为O(1)
        //输入：s = " the sky is blue"
        //输出："blue is sky the"
        public string ReverseWords(string s)
        {
            char[] strArr = s.ToArray();
            //移除多余空格
            strArr = RemoveExtraSpace(strArr);

            //整个翻转
            Array.Reverse(strArr);

            int start = 0;
            for(int i = 0;i<=strArr.Length;i++)
            {
                if (i == strArr.Length || strArr[i] == ' ')
                {
                    //翻转单个单词
                    ReverseWord(strArr, start, i - 1);
                    start = i + 1;
                }
            }
            return new string(strArr);
        }
        
        void ReverseWord(char[] strArr, int start, int end)
        {//翻转单个单词
            int left = start, right = end;
            while(left < right)
            {
                char tmp = strArr[left];
                strArr[left] = strArr[right];
                strArr[right] = tmp;
                left++;
                right--;
            }
        }

        char[] RemoveExtraSpace(char[] strArr)
        {//删除多余空格
            int slowIndex = 0, fastIndex = 0;
            while(fastIndex < strArr.Length)
            {
                //移除开始位置和重复空格
                if (strArr[fastIndex] == ' ' && (fastIndex == 0 || strArr[fastIndex - 1] == ' '))
                    fastIndex++;
                else
                    strArr[slowIndex++] = strArr[fastIndex++];
            }

            //移除末尾空格
            int len = slowIndex;
            if (strArr[slowIndex - 1] == ' ')
                len = slowIndex - 1;
            char[] newArr = new char[len];

            Array.Copy(strArr, newArr,len);
            return newArr;
        }

    }
}
